A system that performs communication based on packets using IP (Internet Protocol) generally uses a communication scheme for performing end-to-end retransmission control using TCP (Transport Control Protocol) in an upper protocol and a communication scheme for not performing retransmission control such as UDP (User Datagram Protocol), TCP is mainly employed when it is necessary to secure reliability in packet communication, for example, when text data such as a web page is transmitted and received or when a file is downloaded from a server. By contrast with this, UDP is employed when packet erasure is acceptable to some degree at the level of an application, for example, when streaming transmission of moving images is performed or speech transmission is performed using VoIP (Voice over IP). Further, if end-to-end retransmission control is employed to perform multicast communication, the number of ACK (Acknowledgement)/NACK (Negative Acknowledgement) signals increase in proportion to the number of receiving terminals and then the network load and the amount of processing in a transmitting-receiving terminal increase, and therefore UDP is employed in this case.
To secure quality in case where a great amount of packet erasure, which is not acceptable at the level of an application, occurs even in moving image streaming or VoIP or to secure reliability in multicast communication, error correction codes are used on an end-to-end basis. For example, Patent Document 1 discloses a communication method for adding redundant packets created using Reed-Solomon codes, to some information packets and transmitting the packets. In this case, even if packet erasure occurs in received packets, a communication apparatus that has received these packets can restore the lost packet within the range of error correction performance of Reed-Solomon codes.
However, error correction is not effective in case where the amount of erasure is beyond correction performance of Reed-Solomon codes or in case where burst erasure occurs in which packets are lost continuously for a comparatively long period due to physical phenomena such as shadowing and fading that occur when a wireless communication channel is used as the medium for performing packet communication. In this case, although it is possible to improve correction performance by increasing a block length of Reed-Solomon code, there is a problem that the amount of operations in encoding/decoding processing and the circuit scale for these operations increase.
In response to this problem, low density parity check (“LDPC”) codes are gaining attention as error correction codes for packet erasure. An LDPC code is a block code that is defined by a very sparse parity check matrix, and allows encoding/decoding processing within a practical period and at a practical operation cost even if the code length is in the order of several thousands to several ten thousands.
FIG. 1 is a conceptual diagram of a communication system utilizing erasure correction coding using an LDPC code. In FIG. 1, a communication apparatus on an encoding side performs LDPC coding of information packets 1 to 4 to be transmitted, to generate redundant packets a and b. An upper layer processing section outputs encoded packets adding redundant packets to information packets, to a lower layer (i.e. the physical layer with the example of FIG. 1), and the physical layer processing section of the lower layer converts the encoded packets in a format that can be transmitted on a communication channel and outputs the encoded packets to the communication channel. FIG. 1 shows an example in case where a communication channel is a wireless communication channel.
The communication apparatus on the decoding side performs receiving processing in the physical layer processing section of the lower layer. At this time, assume that bit error has occurred. Due to this bit error, the packet including that bit that caused error is not reproduced in the upper layer, thereby causing packet erasure. FIG. 1 shows an example of a case where the information packet 3 is lost. The upper layer processing section restores the lost information packet 3 by performing LDPC decoding processing of the received packet sequence.
Generally, the decoding side decodes an LDPC code using an iterative decoding algorithm. An example of an iterative decoding algorithm for an LDPC code for packet erasure correction will be explained using FIG. 2 and FIG. 3. Further, a case will be explained below as an example where a parity check matrix H of an LDPC code is a matrix represented by equation 1.
      [    1    ]                                H          =                      (                                                            1                                                  1                                                  0                                                  1                                                  1                                                  1                                                  1                                                  0                                                  0                                                  0                                                                              1                                                  1                                                  0                                                  0                                                  1                                                  0                                                  0                                                  1                                                  1                                                  1                                                                              1                                                  0                                                  1                                                  0                                                  1                                                  0                                                  1                                                  0                                                  1                                                  1                                                                              0                                                  1                                                  1                                                  1                                                  0                                                  1                                                  0                                                  1                                                  1                                                  0                                                                              0                                                  0                                                  1                                                  1                                                  0                                                  1                                                  1                                                  1                                                  0                                                  1                                                      )                                                (                      Equation            ⁢                                                  ⁢            1                    )                    
FIG. 2 shows the parity check matrix H of equation 1 using a Tanner graph. In this figure, variable nodes represent the relationship in the column direction of the parity check matrix H, and the check nodes represent the relationship in the row direction of the parity check matrix H. Further, in case where the elements in the parity check matrix H are one, a variable node is connected to a check node by a line (i.e. edge). Further, each variable node corresponds to an encoded packet.
FIG. 3 is a flowchart of an iterative decoding algorithm for LDPC decoding. The iterative decoding algorithm will be explained below according to the flowchart. In this figure, ST indicates each step in the flowchart.
In ST11, a received codeword including erasure is inputted to an applicable variable node. In ST12, a check node that is connected with a variable node at which the amount of erasure is one is extracted In case where a check node at which the amount of erasure is one is extracted (ST13: YES), the values of variable nodes that have been correctly received (that are not lost) are subjected to an XOR (exclusive OR) operation in the extracted check node at which the amount of erasure is one. Then, the XOR operation results acquired in ST15 and ST14 are inputted to the variable node that is lost, and the step returns to ST12.
By contrast with this, in case where a check node at which the amount of erasure is one (ST13: NO) is not extracted, whether or not there is erasure in all check nodes is checked, and, if there is not erasure, the decoding algorithm is finished assuming that erasure correction was successful (ST16: YES) or, if there is erasure, the decoding algorithm is finished assuming that erasure correction failed (ST16: NO).
An LDPC code is configured much more flexibly than other codes such as Reed-Solomon codes, and can support various code lengths and coding rates by using different parity check matrices. However, in a system that supports a plurality of code lengths and coding rates, the encoding side and decoding side need to hold a plurality of parity check matrices. In response to this problem, Patent Document 2 discloses an encoding/decoding apparatus that can support a plurality of code lengths using one parity check matrix by adding padding bits to information bit sequences.
Further, to adjust a coding rate, a puncturing method for increasing the coding rate by not transmitting part of redundant packets encoded at a certain coding rate, is generally employed. Puncturing reduces the number of redundant packets and the rate of redundant packets included in an encoded packet sequence, so that it is possible to increase the coding rate. In this case, both the encoding side and decoding side know in advance the positions of redundant packets to puncture, and the decoding side performs decoding processing assuming that punctured packets are lost, so that it is possible to decode codes of various coding rates using a decoding apparatus that supports a certain coding rate. Further, puncturing is employed to adjust coding rates not only in case where error correction coding is performed in packet units but also in case where error correction coding is performed in the physical layer in bit units.    Patent Document 1 Japanese Patent Application Laid-Open No. HE18-186570    Patent Document 2: Japanese Patent Application Laid-Open No. 2006-94012    Non-Patent Document 1: “Finite-Length Analysis of Low-Density Parity-Check Codes on the Binary Erasure Channel,” Changyan Di, David Proietti, I. Emme Telatar, Thomas J. Richardson, and Rudiger L. Urbanke, IEEE Transaction on Information Theory, vol. 48, No. 6, June 2002.